import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 38917
 * Date: 2025-02-14
 * Time: 17:55
 */
public class Sort {
    //插入排序
    /*稳定性:稳定
     * 时间复杂度:
     * 最好:O(N)
     * 最坏:O(N^2)
     * 空间复杂度:O(1)
     */
    public void insertSort(int[] array){
        for (int i = 1; i < array.length; i++) {
            int temp = array[i];
            int j = i - 1;
            for (; j >= 0; j--) {
                if (temp < array[j]){
                    array[j + 1] = array[j];
                }else {
                    break;
                }
            }
            array[j + 1] = temp;
        }
    }
    //希尔排序
    /*稳定性:不稳定
     * 时间复杂度:未知
     * 空间复杂度:O(1)
     */
    public void shellSort(int[] array){
        int gap = array.length;
        while (gap > 1){
            gap = gap / 2;
            shell(array,gap);
        }
    }
    //
    public void shell(int[] array,int gap){
        for (int i = gap; i < array.length; i++) {
            int temp = array[i];
            int j = i - gap;
            for (; j >= 0; j = j - gap) {
                if (temp < array[j]){
                    array[j + gap] = array[j];
                }else {
                    break;
                }
            }
            array[j + gap] = temp;
        }
    }
    //选择排序
    /*稳定性:不稳定
     * 时间复杂度:O(N^2)
     * 空间复杂度:O(1)
     */
    public void selectSort(int[] array){
        for (int i = 0; i < array.length; i++) {
            int minIndex = i;
            for (int j = i + 1; j < array.length; j++) {
                if (array[minIndex] > array[j]){
                    minIndex = j;
                }
            }
            swap(array,i,minIndex);
        }
    }
    //交换
    public void swap(int[] array,int i,int j){
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
    //选择排序2
    /*稳定性:不稳定
     * 时间复杂度:O(N^2)
     * 空间复杂度:O(1)
     */
    public void selectSort2(int[] array){
        for (int i = 0; i < array.length; i++) {
            int minIndex = i;
            int maxIndex = i;
            for (int j = i + 1; j < array.length; j++) {
                if (array[minIndex] > array[j]){
                    minIndex = j;
                }
                if (array[minIndex] < array[j]){
                    maxIndex = j;
                }
            }
            swap(array,i,minIndex);
            if (maxIndex == i){
                maxIndex = minIndex;
            }
            swap(array,array.length - 1,maxIndex);
        }
    }
    //创建大根堆
    public void createHeap(int[] array){
        for (int parent = (array.length - 1 - 1) / 2; parent >= 0; parent--) {
            shiftDown(array,parent,array.length);
        }
    }
    //向下调整
    public void shiftDown(int[]array,int parent,int end){
        int child = (parent * 2) + 1;
        while (child < end){
            if (child + 1 < end && array[child] < array[child + 1]){
                child++;
            }
            if (array[parent] < array[child]){
                swap(array,parent,child);
                parent = child;
                child = (child * 2) + 1;
            }else {
                break;
            }
        }
    }
    //堆排序
    /*稳定性:不稳定
     * 时间复杂度:O(N*logN)
     * 空间复杂度:O(1)
     */
    public void heapSort(int[] array){
        createHeap(array);
        int end = array.length - 1;
        while (end > 0){
            swap(array,0,end);
            shiftDown(array,0,end);
            end--;
        }
    }
    //冒泡排序
    /*稳定性:稳定
     * 时间复杂度:O(N^2)
     * 空间复杂度:O(1)
     */
    public void bubbleSort(int[] array){
        for (int i = 0; i < array.length - 1; i++) {
            boolean flg = false;
            for (int j = 0; j < array.length - 1 - i; j++) {
                if (array[j] > array[j + 1]){
                    swap(array,j,j + 1);
                    flg = true;
                }
            }
            if (!flg) {
                break;
            }
        }
    }
    //快速排序
    /*稳定性:不稳定
     * 时间复杂度:
     * 最好:O(N*logN)
     * 最坏:O(N^2)
     * 空间复杂度:
     * 最好:O(logN)
     *  最坏:O(N)
     */
    public void quickSort(int[] array){
        quick(array,0,array.length - 1);
    }
    //
    public void quick(int[] array,int start,int end){
        if (start >= end) return;

        if(end - start < 15){
            insertSortRange(array,start,end);
            return;
        }

        int index = ave(array,start,end);
        swap(array,index,start);//一定能够保证start下标是中间大的数字

        int pivot = partition2(array,start,end);

        quick(array,start,pivot - 1);
        quick(array,pivot + 1,end);
    }
    //三数取中
    public int ave(int[] array,int right,int left){
        int mid = (right + left) / 2;
        if (array[right] > array[left]){
            if (array[mid] > array[right]) {
                return right;
            } else if (array[mid] < array[left]) {
                return left;
            }else {
                return mid;
            }
        }else {
            if (array[mid] > array[left]){
                return left;
            } else if (array[mid] < array[right]) {
                return right;
            }else {
                return mid;
            }
        }
    }
    //插入排序(自定义范围)
    public void insertSortRange(int[] array,int start,int end){
        for (int i = start + 1; i <= end; i++) {
            int temp = array[i];
            int j = i - 1;
            for (; j >= start; j--) {
                if (temp < array[j]){
                    array[j + 1] = array[j];
                }else {
                    break;
                }
            }
            array[j + 1] = temp;
        }
    }
    //hoare法
    public int partition(int[] array,int left,int right){
        int key = array[left];
        int i = left;
        while (left < right){
            while (left < right && array[right] >= key){//找到比key小的数据
                right--;
            }
            while (left < right && array[left] <= key){//找到比key大的数据
                left++;
            }
            swap(array,left,right);
        }
        swap(array,i,right);
        return left;
    }
    //填坑法
    public int partition2(int[] array,int left,int right){
            int key = array[left];
            while (left < right){
                while (left < right && array[right] >= key){//找到比key小的数据
                    right--;
                }
                array[left] = array[right];
                while (left < right && array[left] <= key){//找到比key大的数据
                    left++;
                }
                array[right] = array[left];
            }
            array[left] = key;
            return left;
    }
    //非递归快速排序
    public void quickSortNor(int[] array){
        Stack<Integer> stack = new Stack<>();
        int left = 0;
        int right = array.length - 1;
        int pivot = partition(array,left,right);

        if (pivot - 1 > left){
            stack.push(left);
            stack.push(pivot - 1);
        }
        if (pivot + 1 < right){
            stack.push(pivot + 1);
            stack.push(right);
        }

        while (!stack.isEmpty()){
            right = stack.pop();
            left = stack.pop();
            pivot = partition(array,left,right);

            if (pivot - 1 > left){
                stack.push(left);
                stack.push(pivot - 1);
            }
            if (pivot + 1 < right){
                stack.push(pivot + 1);
                stack.push(right);
            }
        }
    }
    //归并排序
    /*稳定性:稳定
     * 时间复杂度:O(N*logN)
     * 空间复杂度:O(N)
     */
    public void mergeSort(int[] array){
        mergeSortDivide(array,0,array.length - 1);
    }
    //
    public void mergeSortDivide(int[] array,int left,int right){
        if (left >= right) return;
        int mid = (left + right) / 2;
        mergeSortDivide(array,left,mid);
        mergeSortDivide(array,mid + 1,right);
        mergeSortCombine(array,left,right,mid);
    }
    //合并
    public void mergeSortCombine(int[] array,int left,int right,int mid){
        int[] arrayTemp = new int[right - left + 1];
        int k = 0;
        int start1 = left;
        int start2 = mid + 1;
        while (start1 <= mid && start2 <= right){
            if (array[start1] <= array[start2]){
                arrayTemp[k++] = array[start1++];
            }else {
                arrayTemp[k++] = array[start2++];
            }
        }
        while (start1 <= mid){
            arrayTemp[k++] = array[start1++];
        }
        while (start2 <= right){
            arrayTemp[k++] = array[start2++];
        }
        System.arraycopy(arrayTemp, 0, array, left, arrayTemp.length);
    }
    //非递归归并排序
    public void mergeSortNor(int[] array){
        int gap = 1;
        while (gap < array.length){
            for (int i = 0; i < array.length; i = i + (2 * gap)) {
                //int left = i;
                int mid = i + gap - 1;
                int right = mid + gap;
                if (mid >= array.length){
                    mid = array.length - 1;
                }
                if (right >= array.length){
                    right = array.length - 1;
                }
                mergeSortCombine(array,i,right,mid);
            }
            gap = gap * 2;
        }
    }
    //计数排序
    /*稳定性:稳定(目前代码不稳定)
     * 时间复杂度:O(max(N,范围))
     * 空间复杂度:O(范围)
     */
    public void countSort(int[] array){
        int minVal = array[0];
        int maxVal = array[0];
        for (int i = 1; i < array.length; i++) {
            if (array[i] < minVal) {
                minVal = array[i];
            }
            if (array[i] > maxVal) {
                maxVal = array[i];
            }
        }
        int[] count = new int[maxVal - minVal + 1];
        for (int j : array) {
            count[j - minVal]++;
        }
        int index = 0;
        for (int i = 0; i < count.length; i++) {
            while (count[i] > 0){
                array[index] = i + minVal;
                index++;
                count[i]--;
            }
        }
    }
}














